package solution;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-01-22
 * Time: 16:05
 */

//https://leetcode.cn/problems/insertion-sort-list/submissions/396710055/
class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(4);
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(1);
        ListNode listNode3 = new ListNode(3);
        listNode.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        insertionSortList(listNode);

    }

    public static void insertionSortList(ListNode head) {
        ListNode cur = head.next;
        while (cur != null) {
            ListNode cmp = head;
            int temp = cur.val;
            //该解法能够通过，缺点是本质还是数组赋值（将数值像数组一样挨个移动覆盖）
            //没有利用到链表的插入的快捷行（结点的移动插入）
            //所以虽然思路和题解相同（插入排序），但速度较慢（赋值操作太多）
            while (cmp != cur) {
                if (temp < cmp.val) {
                    int ttemp = cmp.val;
                    cmp.val = temp;
                    temp = ttemp;
                }
                cmp = cmp.next;
            }
            cur.val = temp;
            cur = cur.next;
        }
    }


    public ListNode insertionSortList1(ListNode head) {
        // if (head == null) {//可以省略，但不省略更快
        //     return null;
        // }
        ListNode dummyHead = new ListNode(0, head);
        ListNode lastSorted = head;
        ListNode curr = head.next;
        while (curr != null) {
            if (lastSorted.val <= curr.val) {
                lastSorted = lastSorted.next;
            } else {//利用单链表的插入，减少了赋值的操作，更快
                //单链表只能从头开始遍历
                ListNode prev = dummyHead;
                //因为单链表不能回退，所以必须记录前驱
                while (prev.next.val <= curr.val) {
                    prev = prev.next;
                }
                //curr节点挪到前面，lastSorted连接到后面
                lastSorted.next = curr.next;
                curr.next = prev.next;
                prev.next = curr;
            }
            curr = lastSorted.next;//lastSorted的位置不会改变，但curr可能会插入到前面，所以不能使用curr = curr.next;
        }
        return dummyHead.next;
    }


}
